package nowcoder;

import java.util.ArrayList;
import java.util.List;

/**
 * 亲和数
 */
public class 亲和数 {
    
    public static int sumDivisors(int n) {
        /*
         * 计算n的所有因数之和
         */
        int sum = 1;
        for (int i = 2; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                sum += i;
                if (i != n / i) {
                    sum += n / i;
                }
            }
        }
        return sum;
    }
    
    public static List<int[]> findAmicableNumbers(int limit) {
        /*
         * 查找limit以内的所有亲和数对
         */
        int[] sumDivisors = new int[limit];
        List<int[]> amicableNumbers = new ArrayList<>();
        for (int i = 1; i < limit; i++) {
            sumDivisors[i] = sumDivisors(i);
            if (sumDivisors[i] < limit && sumDivisors[i] != i && sumDivisors[sumDivisors[i]] == i) {
                amicableNumbers.add(new int[]{i, sumDivisors[i]});
            }
        }
        return amicableNumbers;
    }
    
    public static void main(String[] args) {
        List<int[]> amicableNumbers = findAmicableNumbers(500000);
        for (int[] pair : amicableNumbers) {
            System.out.println(pair[0] + " " + pair[1]);
        }
    }
}
